package com.kfm.pm;

public class WordBreak {

    public boolean wordBreak(String s, String[] wordDict) {
        if (s == null || s.isEmpty()) {
            return false;
        }
        // hellocodef h he hel hell hello c co  cod code f
        // "hello", "code"
        // false false false false true false false false true false
        // index 5
        // car ca rs
        // cars c ca r rs
        // false true false true
        // cat sand og c ca cat s sa san sand o og
        // "cats" , "dog" , "sand" , "and" , "cat"
        // false false true false false false true false false
        boolean[] arr = new boolean[s.length() + 1];
        arr[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            inner:
            for (int j = 0; j < i; j++) {
                String str = s.substring(j, i);
                for (int k = 0; k < wordDict.length; k++) {
                    if (wordDict[k].equals(str) && arr[j]) {
                        arr[i] = true;
                        break inner;
                    }
                }
            }

        }
        return arr[s.length()];
    }

    public static void main(String[] args) {
        WordBreak wordBreak = new WordBreak();
        String string = "helloworld";
        String[] wordDict = {"helloworld", "hello"};
        System.out.println(wordBreak.wordBreak(string, wordDict));  // 输出: true
    }
}